package anagramaa;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

/**
 * 
 * @author Carolina Lorini
 * @author Felipe Wilke
 * @author Jonas Jeske
 * 
 */
public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Main anagram = new Main();
		anagram.begin();
	}

	public void begin() {

		// variaveis de entrada
		int numeroDePalavras;
		ArrayList<String> palavras = new ArrayList<String>();
		StringTokenizer linhaStringTokenizer;
		String linhaDigitada, palavra;

		// enquanto for verdadeiro
		//while (true) {

			StringBuffer sb = new StringBuffer();
			
			// le o numero de palavras
			// busca a linha digitada
			linhaDigitada = retornaLinhaDigitada(2500);

			// transforma em tokens
			linhaStringTokenizer = new StringTokenizer(linhaDigitada);

			// pega os primeiros elementos, referente ao numero de linhas e
			// colunas
			numeroDePalavras = Integer.parseInt(linhaStringTokenizer
					.nextToken());

			// se o numero de palavras
			if (numeroDePalavras > 0) {

				// le as palavras
				for (int i = 0; i < numeroDePalavras; i++) {

					// le o numero de palavras
					// busca a linha digitada
					linhaDigitada = retornaLinhaDigitada(2500);

					// transforma em tokens
					linhaStringTokenizer = new StringTokenizer(linhaDigitada);

					// pega os primeiros elementos, referente ao numero de
					// linhas e colunas
					palavra = linhaStringTokenizer.nextToken();
					palavras.add(ordenaCaracteresPalavra(palavra));
				}
				
				ArrayList<String> palavrasFinais = new ArrayList<String>();
				
				//para cada palavra, realiza a permutacao
				for(String p:palavras){
					//System.out.println("Passando pela palavra..");
					ArrayList<String> palavrasPermutadas = new ArrayList<String>();
					permutaPalavra(p.toCharArray(), 0, p.length(),palavrasPermutadas);
					
					//ordena lista
					Collections.sort(palavrasPermutadas);
					for(String pBuffer: palavrasPermutadas){
						if(!palavrasFinais.contains(pBuffer)){
							palavrasFinais.add(pBuffer);
							
						}
						
					}
				}
				
				boolean primeiro = true;
				for(String pal:palavrasFinais){
					if(primeiro){
						sb.append(pal);
						primeiro = false;
					}else{
						sb.append("\n"+pal);
					}
					
				}
				
				System.out.print(sb.toString());
				//break;
				
			}else{
				//break;
			}
		//}
	}

	public static void troca(char[] palavra, int primeiroChar, int segundoChar)
	{
		char ch = palavra[segundoChar]; 
		palavra[segundoChar] = palavra[primeiroChar]; 
		palavra[primeiroChar] = ch;
	}

	public static int permutaPalavra(char[] palavra, int indexInicio, int indexFinal,ArrayList<String> listaPalavrasPermutadas) {
		int i;
		int diferenca = indexFinal - indexInicio;
		if (diferenca == 1) {
			//System.out.println(palavra);
			listaPalavrasPermutadas.add(new String(palavra));
		} else {
			for (i = 0; i < diferenca; i++) {
				troca(palavra, indexInicio, indexInicio + i);
				permutaPalavra(palavra, indexInicio + 1, indexFinal,listaPalavrasPermutadas);
				troca(palavra, indexInicio, indexInicio + i);
			}
		}
		return 0;
	}

	public String ordenaCaracteresPalavra(String palavra) {
		String buffer = "";
		ArrayList<Character> listaChar = new ArrayList<Character>();
		for (int p = 0; p < palavra.length(); p++) {
			listaChar.add(new Character(palavra.charAt(p)));
		}
		Collections.sort(listaChar);
		// System.out.println("\nImprimindo lista char: ");
		for (int i = 0; i < listaChar.size(); i++) {
			// System.out.print(listaChar.get(i)+" - ");
			buffer += listaChar.get(i).charValue();
		}
		return buffer;
	}

	public void imprimeLista(ArrayList<String> lista) {
		System.out.println("\nImprimindo lista:");
		for (String p : lista) {
			System.out.print(p + " - ");
		}
	}

	/**
	 * Retorna a linha digitada no input.
	 * 
	 * @param tamanhoMaximo
	 * @return
	 */
	static String retornaLinhaDigitada(int tamanhoMaximo) {

		// armazena em um array o input
		byte linha[] = new byte[tamanhoMaximo];
		int indexCaracterNaLinha = 0, caracterDigitado = -1;
		try {
			// enquanto nao atingir o numero max de caracteres
			while (indexCaracterNaLinha < tamanhoMaximo) {

				// armazena o caracter digitado
				caracterDigitado = retornaCaracterDigitado();

				// se for menor que zero ou fim de linha, para de ler
				if ((caracterDigitado < 0) || (caracterDigitado == '\n')) {
					break;
				}

				// armazena o caracter digitado na linha
				linha[indexCaracterNaLinha++] += caracterDigitado;
			}
		} catch (IOException e) {
			return (null);
		}

		// se for caracter invalido, retorna zero
		if ((caracterDigitado < 0) && (indexCaracterNaLinha == 0)) {
			return (null); // eof
		}

		// senao retorna a string lida
		return (new String(linha, 0, indexCaracterNaLinha));
	}

	/**
	 * Retorna o caracter digitado.
	 * 
	 * @return
	 * @throws IOException
	 */
	static int retornaCaracterDigitado() throws IOException {
		return System.in.read();
	}
}

